#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
class Solution {

public:
    Solution()
    {
        _dest = 0;
        _cur = 0;
    }
    int checkzero(vector<int>& arr, int final)
    {
        int cnt = 0;
        for (int i = 0; i <= final; i++)
        {
            if (arr[i] == 0)
                cnt++;
        }
        return cnt;
    }
    void duplicateZeros(vector<int>& arr) {
        int number = 0;
        while (_dest < (int)arr.size() - 1)
        {
            if (arr[_cur] != 0)
            {
                _dest++;
                if (_dest < arr.size())
                    _cur++;
            }
            else {
                _dest += 2;
                if (_dest < arr.size())
                    _cur++;
            }
        }
        number = checkzero(arr, _cur);
        if (_dest == arr.size())
            --_dest;
        if (_cur + number > _dest)
        {
            arr[_dest--] = arr[_cur--];
        }

        while (_cur != _dest)
        {


            if (arr[_cur] != 0)
                arr[_dest--] = arr[_cur--];
            else
            {
                arr[_dest--] = arr[_cur];
                arr[_dest--] = arr[_cur--];
            }
        }
    }
private:
    int _dest;
    int _cur;
};
int main()
{
    vector<int> a;
    a.push_back(1);
    a.push_back(5);
    a.push_back(2);
    a.push_back(0);
    a.push_back(6);
    a.push_back(8);
    a.push_back(0);
    a.push_back(6);
    a.push_back(0);

    /* a.push_back(8);
     a.push_back(0);
     a.push_back(6);
   */


    Solution().duplicateZeros(a);
    for (auto& e : a)
    {
        cout << e << " ";
    }
}